/**
 * 
 */
package integercoding;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @author ricardo
 * 
 */
public class FibonacciCoding {

	public static String encode(int number, int order) {
		assert number > 0 : "Number must be positive";
		assert order >= 2 : "Order must be greater than 2";
		String result = "";
		ArrayList<Integer> fibs = new ArrayList<>();
		// find the fibbonacci series until number
		if (number >= 1) {
			int a = 1;
			int b = 1;
			int c = a + b;
			fibs.add(b);
			while (number >= c) {
				fibs.add(c);
				a = b;
				b = c;
				c = a + b;
			}
			// append the m-1 1's to the codeword
			for (int i = 0; i < order - 1; i++)
				result += "1";
			Collections.reverse(fibs);
			// complete the codeword
			for (Integer fibnum : fibs) {
				// if the number is greater than the current fibonacci Number
				// add a one to the start of the code
				if (number >= fibnum) {
					number -= fibnum;
					result = "1" + result;
					// else add a zero
				} else {
					result = "0" + result;
				}
			}
		}
		return result;
	}
}
